package com.leetcode.BinaryTree;

//二叉树的直径
public class lc_543 {
    public static void main(String[] args) {

    }

    //1.判断:维护一个int型全局变量,需要重构一个方法
    //ans在这里代表这棵树的最大节点数 = 左子树最大节点数 + 右子树最大节点数 + 1
    int ans = -1;
    public int diameterOfBinaryTree(TreeNode root){
        dfs(root);
        //最大直径 = 最大节点数 - 1
        return ans - 1;
    }

    //2.传入参数:这棵树的根结点root  返回参数:这棵树的最大节点数(只包括左右子树中的一棵)
    private int dfs(TreeNode root) {
        //3.边界条件:
        if(root == null){
            return 0;
        }
        //4.每层逻辑:根据传入参数和返回参数
        //4.1.先求出左右子树的最大节点数
        int left = dfs(root.left);
        int right = dfs(root.right);
        //4.2.更新此时最大的结点数ans:max(之前的结点数,左子树结点+右子树结点+根节点)
        ans = Math.max(ans, left + right + 1);
        //4.3.返回这棵树的最大节点数:max(左子树节点数,右子树节点数)+根节点
        return Math.max(left,right) + 1;
    }
}
